package 链表;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * https://leetcode-cn.com/problems/merge-k-sorted-lists/
 */
public class _23_合并K个升序链表 {
    public class ListNode {
       int val;
       ListNode next;
       ListNode() {}
       ListNode(int val) { this.val = val; }
       ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0 || lists == null) return null;
        ListNode newList = new ListNode(0);
        ListNode p = newList;
        //创建一个大小为lists.length的最小堆
        PriorityQueue<ListNode> heap = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });

        //将每个链表的头节点放入最小堆中
        for (ListNode head : lists) {
            if(head!=null){
                heap.add(head);
            }
        }

        //从最小堆中取出最小的链表节点,连接到结果链表上
        while(!heap.isEmpty()){
            ListNode node = heap.poll();
            p.next = node;
            //将每个链表的后序节点加入最小堆中并继续取出最小值的节点
            if(node.next!=null){
                heap.add(node.next);
            }
            p = p.next;
        }
        return newList.next;
    }
}
